1. Field of the Invention
The present invention relates to paging data storage systems employing a backing store, such as a DASD (Direct Access Storage Device), and a front store, serving as a cache, and preferably consisting of a random access memory.
2. Description of the Prior Art
Paging and swapping stores have taken several configurations; for example, various direct access storage devices have been used directly for storing paging and swapping data. The problem concerned with useind such devices is the relatively long access time to stored paging and swapping data which may have an adverse effect on the total central processing unit or data processing system performance. The IBM 2305 Fixed Head Storage Module described in publication GA-26-1589, available from International Business Machines Corporation, Armonk, N.Y., describes a data storage drum for use in a paging and swapping environment. An advantage of the storage drum over and above the direct access storage devices is the relatively fast access to the paging and swapping data signals. A disadvantage is the relatively high cost for a given capacity of the storage drum. Accordingly, in many paging and swapping applications, a storage drum such as the IBM 2305 unit stores active pages of data while the relatively inactive data was kept on direct access storage devices. Accordingly, a hierarchical paging storing system which automatically transfers instruction, paging and spooling data between a front store, which has high speed accesses, and a backing store having relatively large capacity and lower cost, hence a longer access, is desired.
Further, multiple exposures to the data is to be provided. That is, more than one address should be usable to access a given unit of data. In this regard, the IBM 2305 unit supported multiple requesting in that addresses 0-7 cause access to a magnetic storage drum having a physical address of 0 while addresses in the group 8-15 select the drum module having a physical address 8. Each drum, of course, could honor only one access at a given time; therefore, a given access through one of the addresses for a given drum module would place all of the addresses to that given drum module in a so-called busy or non-accessible state. A greater flexibility in the multiple addressing area is desired for enhancing execution of programs of instructions and transferring paging and swapping data sets.
Hierarchical data stores for diverse applications have been employed with diverse backing stores, for example, backing stores can be in the form of magnetic tape recorders, magnetic disk storage apparatus, such as direct access storage devices (DASD), relatively slow volatile random access memories, magnetic bubble or shift register type of memories, tape library systems and the like. Front stores, which are designed to mask the relatively long access times to a backing store have also taken diverse types of configurations. For example, in the IBM 3850 Mass Storage System, a backing store consisted of a magnetic tape library while a front store consisted of a plurality of direct access storages devices. Here, the access to the direct access storage devices was relatively fast when compared with access to data stored in a data cartridge contained in the automatic tape library.
In the Eden U.S. Pat. No. 3,569,938, a hierarchical store is presented as being an apparent store to a using data processing system. A cache concept is shown in this patent wherein a relatively high speed store acts as a buffer to a relatively slow access store. In this instance, a random access memory serves as a front store or cache while the backing store is either tape or disk data storage apparatus. The size of the apparent store was the capacity of the backing store while the access time gave an apparent access equal to the rapid access of the front store. Another hierarchical store is shown in Spencer, U.S. Pat. No. 3,839,704, wherein a direct access storage device is buffered by a random access memory which is accessible via a directory structure. The directory structure interprets the addresses for the backing direct access storage device and converts same to a buffer address through table lookup mechanisms well known in the data processing art. Again, the purpose of the Spencer arrangement was to mask a relatively long access to the direct access storage unit. Spencer also provided for transferring data from the direct access storage devices to the buffer before the data processing system, connected to this hierarchical store, needed the data such that access time to the data was minimized. These two patents show general arrangements for caching various types of peripheral storage devices. Further controls are still needed for satisfying modern day requirements of a paging and swapping storage system.
Another technological area in which caching enhances performance is found in the main memory area of a computer or central processing unit. That is, each data processing system includes a central processing unit that has a cache or high speed store. The backing store for this cache is the usual main memory. Various techniques have been used for enhancing the caching operation such that the central processing unit instruction execution, as well as operand data transfers, are maximized. An example of controlling the operation of a cache with respect to a central processing unit and a main memory is shown in Calle, et al, U.S. Pat. No. 4,075,686. This U.S. patent teaches that it is not always wise to use the cache; that in some instances, performance can be enhanced by bypassing the cache. Cache bypass is achieved in one of several ways. In one example, the main memory is arranged in segments. Some of those segments can be dedicated for input/output or peripheral operations. All accesses to those segments bypass the main memory cache. In a similar manner, the cache for a direct access storage device could be bypassed for selected devices or portions of devices under certain circumstances. In another aspect of Calle, performance enhancement can be achieved by selectively bypassing cache on a command basis. In this instance, the command to the main memory area contains a cache bypass bit. When the bit is set to unity, the cache is not used (the main memory is directly accessed). When the cache bypass bit is reset to zero, then the cache is used. While selective bypassing a cache can, in many instances, optimize performance of a data storage system, such as the main memory cache system or a DASD-cache system, further controls appear to be necessary for meeting the stringent requirements of modern day paging and swapping data transfers.
In a data storage hierarchy having multiple paths between devices in the hierarchy, the data movements can be advantageously load balanced to enhance performance. Also when volatile data storage units are employed in some levels of the hierarchy, storage system and data availability can be enhanced by such load balancing.
Balancing data processing loads between a plurality of units usually occurs at so-called task assignment time. That is, before data processing work ensues, a control mechanism determines which unit should do the task; once the task is assigned to a unit, that unit continues to operate even though later it may be more heavily loaded than other units in the system. An example of such task assignment balancing is found in the IBM Technical Disclosure Bulletin, Vol. 20, No. 3, August 1977, pp. 937-938, in the article entitled "Load Balancing Control for a Multi-processor", by J. F. Baker and D. E. Holst. This article describes a loosely-coupled multi-processor control storage and memory system having load balance tables in various processors controlling the system. Load balance is achieved at assignment time to operate even though it may be more heavily loaded than other units in the system. Load balance is achieved at assignment time based upon load balance tables which indicate a measurement of work queue depth. Load balance information is exchanged between the various processors of the memory system. The scheduling of timed processes is also described. Another example of load balancing at task assignment time is found in a similar IBM Technical Disclosure Bulletin article, Vol. 14, No. 11, April 1972, entitled "Input/Output Channel/Device Load Balancing Algorithm," by L. A. Jaikes, et al, wherein a peripheral subsystem has its work balanced at work assignment time.
Central processors or hosts in a multi-processing arrangement also often load balance at task assignment time. An example is shown in U.S. Pat. No. 3,648,253 which shows tasks being assigned in a multi-processor arrangement by a programmed scheduler as later described with respect to FIG. 15 and based upon time to go on to a present task. The balancing of work loads is by assignment of tasks before the tasks are initiated. U.S. Pat. No. 4,032,899 shows a data switching network which balances data traffic on an aggregate processing load. This balancing is achieved by scheduling output traffic to ports by individual processors on an exclusive assignment basis; i.e., load balancing again is achieved when the task to be performed is first assigned.
Load balancing also has been achieved upon detection of an error condition; for example, U.S. Pat. No. 3,787,816 shows a multi-processing system which may be reconfigured in a controlled manner to redesignate the functions assigned to particular similar units so as to provide continued data processing capabilities after a malfunction or error.
Activity monitors have been employed for balancing loads. U.S. Pat. No. 3,588,837 shows a system for measuring activity of all major data paths using a time interval utilization sampling technique. The samples are dynamically recorded to represent the ratio of number of samples for revealing the number of samples in one time interval compared with the number of samples taken during an earlier time interval whereby the activity of all potential queuing points within a dynamic environment are recorded to provide statistical data concerning utilization of data processing and communication equipment. This patent shows a measurement system but not load balancing which could be driven by such a measurement system.
Not all work load balancing has been achieved at assignment time; for example, U.S. Pat. No. 4,099,235 shows a method of operating a data processing system having two real-time data processors wherein given tasks are selectively performed in one of the data processors. Such a selection depends upon the character of the task and which processor has been selected to operate on such tasks. Each of the data processors is continuously monitored for the purpose of continually determining its utilization ratio. Each processor is assigned a predetermined upper limit value of such utilization ratio which lies below the processor's overload limit. Whenever such upper limit is exceeded, the tasks being performed in the one busy data processor are diverted to another data processor such that the receiving or another processor performs the diverted task. This patent shows a utilization threshold as a method of instigating shifting of ongoing tasks between data processors. The disclosed method is preferably a ratio of the waiting time resulting from tasks being performed to the free time for indicating utilization ratio. This patent also refers to U.S. Pat. No. 3,665,404 wherein peripheral devices are switched between data processors by means of electro-mechanical switch in connection with balancing the input/output load between these processors. According to U.S. Pat. No. 4,099,235, many of the real-time operations are similar to batch processing; accordingly, tasks that are not currently being operated upon can be readily transferred between the processors. This means that only inactive tasks are transferred for purpose of a load balancing.
In a dynamic data processing system where activity can vary beyond a control of the controlling data processors, load balancing between the various data processors/data processing paths should fully accommodate subsequent unforeseen dynamic changes in activities such that data transfers for load balancing are minimized for maximizing data processing throughput.
In a paging and swapping environment, it is desired that plural accesses be provided for multitasking paging access while minimizing host controls over the storage system; that is, the paging and swapping storage system should have a good set of controls for maximizing the host or central processing unit operations while maintaining continuity of each independent operation for ensuring integrity of the paging and swapping environment. Balancing asynchronous operations between units in the environment can aid data storage system availability.